#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node* next;

    Node()
    {
        data = 0;
        next = nullptr;
    }

    Node(int x, Node* p = nullptr)
    {
        data = x;
        next = p;
    }
};

Node* insert_first(Node* head, int x)
{
    Node* p = new Node(x, head);
    return p;
}

Node* insert_last(Node* head, int x)
{
    if (head == nullptr)
        return new Node(x);
    head->next = insert_last(head->next, x);
    return head;
}

Node* insert(Node* head, int k, int x)
{
    if (k == 0)
        return new Node(x, head);
    head->next = insert(head->next, k - 1, x);
    return head;
}

Node* erase_first(Node* head, int &e)
{
    if (head == nullptr)
    {
        e = ~(1 << 31);
        return nullptr;
    }
    e = head->data;
    Node* tmp = head->next;
    delete head;
    return tmp;
}

Node* erase_last(Node* head, int& e)
{
    if (head == nullptr)
    {
        e = ~(1<<31);
        return nullptr;
    }

    if (head->next == nullptr)
    {
        e = head->data;
        Node* tmp = head->next;
        delete head;
        return tmp;
    }

    head->next = erase_last(head->next, e);
    return head;
}

Node* erase(Node* head, int k, int& e)
{
    if (head == nullptr)
    {
        e = ~(1<<31);
        return head;
    }
    if (k == 1)
    {
        e = head->data;
        Node* tmp = head->next;
        delete head;
        return tmp;
    }
    head->next = erase(head->next, k - 1, e);
    return head;
}

int query_first(Node* head)
{
    if (head)
        return head->data;
    return ~(1<<31);
}

int query_last(Node* head)
{
    if (head == nullptr)
        return ~(1<<31);
    if (head->next == nullptr)
        return head->data;
    return query_last(head->next);
}

int query(Node* head, int k)
{
    if (head == nullptr)
        return ~(1<<31);
    if (k == 1)
        return head->data;
    return query(head->next, k - 1);
}

Node* reverse(Node* head)
{
    if (head == nullptr || head->next == nullptr)
        return head;
    Node* tmp = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    return tmp;
}

void show(Node* head)
{
    if (head == nullptr)
        return;
    printf("%d ", head->data);
    show(head->next);
}

void destroy(Node* head)
{
    if (head == nullptr)
        return;
    destroy(head->next);
    delete head;
}